package org.kth.dks.dks_node;

/**
 * <p>Title: DKS</p>
 * <p>Description: DKS Middleware</p>
 * <p>Copyright: Copyright (c) 2004</p>
 * <p>Company: KTH-IMIT/SICS</p>
 * @author not attributable
 * @version 1.0
 */

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

import org.kth.dks.util.MathMiscConstant;

public class IntervalOptimizer {

  private final MathMiscConstant math;

  /**
   * Constructor taking a reference to the dks Math library
   * @param math MathMiscConstant an already initialized DKS math library
   */
  public IntervalOptimizer(MathMiscConstant math) {
    this.math = math;
  }

  /**
   * INTERNAL. Takes an interval <i>i</i> and a List of intervals, iterates and MODIFIES the
   * List of intervals to make sure that <i>i</i> is collapsed into any existing interval.
   * @param i Interval to be merged with the existing intervals
   * @param workListRest List will be MODIFIED if <i>i</i> overlaps with any of its intervals
   * @return boolean true if the list has not been modified at all
   */
  private boolean iterate(Interval i, List workListRest) {
    List tempList = new ArrayList();
    boolean dirty = false;
    for (Iterator inter = workListRest.iterator(); inter.hasNext(); ) {
      Interval curr = (Interval) inter.next();
      if (!math.belongsTo(i.start, curr.start, curr.end) &&
          !math.belongsToII(i.end, curr.start, curr.end) &&
          !math.belongsTo(curr.start, i.start, i.end) &&
          !math.belongsToII(curr.end, i.start, i.end)) {
        tempList.add(curr);
      }
      else if (!math.belongsTo(i.start, curr.start, curr.end) &&
               !math.belongsToII(i.end, curr.start, curr.end)) {
        dirty=true;
        tempList.add(curr);
        tempList.add(i);
      }
      else if (!math.belongsTo(i.start, curr.start, curr.end) &&
               math.belongsToII(i.end, curr.start, curr.end)) {
        dirty=true;
        tempList.add(new Interval(i.start, curr.end));
      }
      else if (math.belongsTo(i.start, curr.start, curr.end) &&
               !math.belongsToII(i.end, curr.start, curr.end)) {
        dirty=true;
        tempList.add(new Interval(curr.start, i.end));
      }
      else if (math.belongsTo(i.start, curr.start, curr.end) &&
              math.belongsToII(i.end, curr.start, curr.end) &&
              math.belongsTo(curr.start, i.start, i.end) &&
              math.belongsToII(curr.end, i.start, i.end) ) {
       dirty=true;
       tempList.add(new Interval(0,math.modMinus(0,1)));
     }
     else if (math.belongsTo(i.start, curr.start, curr.end) &&
               math.belongsToII(i.end, curr.start, curr.end)) {
        dirty=true;
        tempList.add(curr);
      }
    }
    workListRest.clear();
    workListRest.addAll(tempList);
    return dirty;
  }

  /**
   * Takes a list of Interval's and returns a new list of Intervals guaranteeing
   * that subsumed Intervals have been removed and partially overlapping intervals
   * have been collapsed/merged.
   * @param intervalList List of Intervals
   * @return List flattened/collapsed list of Intervals
   */
  public List collapseIntervals(List intervalList) {
    List workList = new LinkedList(intervalList);
    List finalList = new LinkedList();
    while (!workList.isEmpty()) {
      if (workList.size()==1) {
        List tmp = new LinkedList(workList);
        tmp.addAll(finalList);
        finalList = tmp;
        workList.clear();
      } else {
        Interval head = (Interval) workList.remove(0);
        boolean dirty = iterate(head, workList);
        if (!dirty)
          finalList.add(head);
      }
    }
    return finalList;
  }

  /**
   * Takes a List of intervals and returns a new List containing intervals which
   * are guaranteed to not contain anything from the Interval rem.
   * @param list List containing Intervals
   * @param rem Interval specifies the interval to be removed
   * @return List a new intervals with same intervals as list, but where the interval rem has been removed
   */
  public List removeInterval(List list, Interval rem) {
    List newList = new LinkedList();
    for (ListIterator iter=list.listIterator(); iter.hasNext(); ) {
      Interval curr = (Interval) iter.next();

      if (math.belongsToII(curr.start, rem.start, rem.end) &&
          math.belongsToII(curr.end, rem.start, rem.end) &&
          math.distanceClockWise(rem.start, curr.end) <
          math.distanceClockWise(rem.start, curr.start)
          ) {
        newList.add(new Interval(rem.end, rem.start));

      }
      else if (math.belongsToII(curr.start, rem.start, rem.end) &&
          math.belongsToII(curr.end, rem.start, rem.end)) {
        newList=newList;
      } else if (!math.belongsToII(rem.start, curr.start, curr.end) &&
                 !math.belongsToII(rem.end, curr.start, curr.end)) {
        newList.add(curr);
      } else {
        if (math.belongsTo(rem.start, curr.start, curr.end)) {
          newList.add(new Interval(curr.start, rem.start));
        }
        if (math.belongsToI(rem.end, curr.start, curr.end)) {
          newList.add(new Interval(rem.end, curr.end));
        }
      }
    }
    return newList;
  }

  // TESTING PURPOSES ONLY
  public static void main(String []arg) {
    IntervalOptimizer i = new IntervalOptimizer(new MathMiscConstant(1073741824, 2));

    List ints = new LinkedList();

    ints.add(new Interval(536871413, 536870913));
    ints.add(new Interval(805306869, 805306369));
    ints.add(new Interval(939524597, 939524097));
    ints.add(new Interval(1006633461, 1006632961));
    ints.add(new Interval(1040187893, 1040187393));
    ints.add(new Interval(1056965109, 1056964609));
    ints.add(new Interval(1065353717, 1065353217));
    ints.add(new Interval(1069548021, 1069547521));
    ints.add(new Interval(1071645173, 1071644673));
    ints.add(new Interval(1072693749, 1072693249));
    ints.add(new Interval(1073218037, 1073217537));
    ints.add(new Interval(1073480181, 1073479681));
    ints.add(new Interval(1073611253, 1073610753));
    ints.add(new Interval(1073676789, 1073676289));
    ints.add(new Interval(1073709557, 1073709057));
    ints.add(new Interval(1073725941, 1073725441));
    ints.add(new Interval(1073734133, 1073733633));
    ints.add(new Interval(1073738229, 1073737729));
    ints.add(new Interval(1073740277, 1073739777));
    ints.add(new Interval(1073741301, 1073740801));
    ints.add(new Interval(1073741813, 1073741313));
    ints.add(new Interval(245, 1073741569));
    ints.add(new Interval(373, 1073741697));
    ints.add(new Interval(437, 1073741761));
    ints.add(new Interval(469, 1073741793));
    ints.add(new Interval(485, 1073741809));
    ints.add(new Interval(493, 1073741817));
    ints.add(new Interval(497, 1073741821));
    ints.add(new Interval(499, 1073741823));
    ints.add(new Interval(500, 0));

    List newints = i.collapseIntervals(ints);
    List newints2 = i.removeInterval(newints, new Interval(500,0));

    for (Iterator it=newints2.iterator(); it.hasNext();) {
      Interval iv = (Interval) it.next();
      System.out.println("Interval "+iv);
    }

    System.out.println("");
  }

}
